package cn.com.yang.datastruct.list;

/**
 * @Desc<约瑟夫问题>
 * @Author 杨亿金
 * @Date 2020/12/11 10:05
 * @CopyRight
 * @Version
 */
public class CircleLinkedList {

    /**
     * 约瑟夫问题：n个人围城一个圆圈，从第m个人开始数 每次数到k出局，直到最后剩余一个人
     *
     * @param n 一共n个人围城一个圆
     * @param k 一次数k个人杀掉
     */
    public static void killCount(int n, int k) {
        //头结点不存储数据
        Node head = new Node();
        Node cur = head;
        //循环构造这个链表 人从1开始~n
        for (int i = 1; i <= n; i++) {
            Node node = new Node(i);
            cur.next = node;
            cur = node;
        }
        //链表有数据的部分首尾相连形成一个环。
        cur.next = head.next;
        //统计开始的时候，刨去头结点，然后从第一个有数据的结点开始报数
        //相当于指针
        Node p = head.next;
        //循环退出的条件是最后只剩一个结点，也就是这个结点的下一个结点是它本身
        while (p.next != p) {
            //正常报数的遍历逻辑
            for (int i = 1; i < k - 1; i++) {
                p = p.next;
            }
            //当数到k的时候，出局
            System.out.print(p.next.n + " > ");
            int j = 1;
            do {
                dealK(p,p.next);

                j++;
            } while (j <= k);
            // p.next = p.next.next;
            p.next = p.next.next;
            p = p.next;
        }
        //最后剩下的一个结点
        System.out.println("(live:" + p.n + ")");

    }
    static void dealK(Node p,Node m){
        p = m.next;
    }
    public static void main(String[] args) {
        killCount(4, 3);
    }
}

class Node {
    int n;
    Node next;

    public Node() {
    }

    public Node(int n) {
        this.n = n;
    }

}

